package or;

import org.junit.jupiter.api.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class T1653 {

    public int minimumDeletions3(String s) {
        int leftb=0;
        int n=0;
        for (int i = 0; i <s.length() ; i++) {
            if (s.charAt(i)=='b'){
                leftb++;
            }else {
                n=Math.min(n+1,leftb);
            }
        }
        return n;
    }
    public int minimumDeletions2(String s) {
        int leftb = 0, righta = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                righta++;
            }
        }
        res = righta;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                righta--;
            } else {
                leftb++;
            }

            res = Math.min(res, leftb + righta);
        }
        return res;
    }


    public int minimumDeletions(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        int left, right;
        if (s.contains("b") && s.contains("everyday3")) {
            left = s.indexOf('b');
            right = s.lastIndexOf('a');
        } else {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        stack.add(0);
        queue.add(0);
        int min = Integer.MAX_VALUE;
        int leftT = left;
        int t = 0;
        while (leftT < right) {
            int sum = 0;
            while (s.charAt(leftT) == 'b') {
                sum++;
                leftT++;
            }
            if (sum != 0) {
                t += sum;
                stack.add(t);
            }
            leftT++;
        }
        int rightT = right;
        t = 0;
        while (left < rightT) {
            int sum = 0;
            while (s.charAt(rightT) == 'a') {
                sum++;
                rightT--;
            }
            if (sum != 0) {
                t += sum;
                queue.add(t);
            }
            rightT--;
        }
        while (!stack.empty()) {
            min = Math.min(min, stack.pop() + queue.poll());
        }
        return min;


    }


    @Test
    public void test() {
        String str = "aababbab";
        int re = minimumDeletions(str);
        System.out.println(re);

    }


}
